package com.fr.lintcode;

public class Q1753 {

    /**
     * @param cost: the cost
     * @param val: the val
     * @return: the all cost
     */
    public long doingHomework(int[] cost, int[] val) {
        // Write your code here.
    	if(cost == null || cost.length == 0) {
    		return 0;
    	}
    	int length = cost.length;
    	long [] sum = new long[length];
    	sum[0] = cost[0];
    	for(int i = 1; i < length; i ++) {
    		sum[i] = sum[i - 1] + cost[i];
    	}
    	long count = 0;
    	for(int v : val) {
    		count += getBigNum(sum, v);
    	}
    	return count;
    }

	private long getBigNum(long[] sum, int v) {
		int low = 0;
		int high = sum.length - 1;
		int mid = -1;
		while(low <= high) {
			mid = (low + high) / 2;
			if(sum[mid] > v) {
				high = mid - 1;
			}else if(sum[mid] == v){
				return sum[mid];
			}else {
				low = mid + 1;
			}
		}
		if(sum[mid] > v) {
			if(mid < 1) {
				return 0;
			}else {
				return sum[mid - 1];
			}
		}else {
			return sum[mid];
		}
	}


}
